By way of introduction, secure systems typically use passwords (textual and/or binary) to control access to system resources. In a basic system, the password is typically stored in the system for authenticating a candidate password by comparing the received candidate password against the stored password. A vulnerability of the basic system is that an attacker who obtains access to the system can find the stored password and use it at a later point to access the system.
A common solution to the above problem is to calculate a hash value of the password using a hash function and then store the hash value. A candidate password received by the system is first processed by the hash function giving an output value. The output value is then compared to the stored hash value. Therefore, an attacker that penetrates the system will only find the hash value which cannot be used as the access password.
The stored hash value is preferably stored in non-volatile memory (NVM) for example, but not limited to, fuses and OTP (one-time programmable) memory. In many devices the available NVM is typically limited and therefore it is desirable to keep the amount of storage space used for the stored hash value as small as possible. However, reducing the size of the stored hash value normally means reducing the security level provided by the hash value, as will be explained below.
When a typical hash function maps a password (input value) to a hash value (output value), the security of the system is proportional to the number of bits of the hash value. For example, if the hash value has 32 bits, then on average it takes 232 (approximately 4 billion) trials in order to find a password (which is not necessarily the original password) that maps to the hash value using the hash function.
Therefore, it takes approximately 4 billion trials for an attacker to find a password which maps to the stored hash value. The exact time it takes to perform 4 billion trials depends on the speed of the processor being used as well as the complexity of the hash function. Nevertheless, 4 billion trials would not take very long using a standard personal computer and therefore a 32 bit hash value probably does not provide sufficient security for most scenarios. Therefore, the hash value needs to be long enough to ensure sufficient security.
Therefore, there is a tradeoff between security and cost of the storage space.
The following reference is believed to represent the state of the art:
US Published Patent Application 2005/0250473 of Brown, et al.
The disclosures of the references mentioned above and throughout the present specification, as well as the disclosures of all references mentioned in the references, are hereby incorporated herein by reference.